//
// Created by Administrator on 2021/6/11.
//
#include <iostream>
#include <unordered_set>
#include <climits>
#include <vector>

using namespace std;

class Solution {
private:
    unordered_set<int> square_nums;
public:
    int numSquares(int n) {
        for (int i = 1; i * i <= n; ++i) {
            this->square_nums.insert(i * i);
        }
        for (int count = 1; count <= n; ++count) {
            if (is_divided(n, count)) return count;
        }
        return n; // 一般到不了这里
    }

    bool is_divided(int n, int count) {
        /**return: true if "n" can be decomposed into "count" number of perfect square numbers.
                e.g. n=12, count=3:  true.
                n=12, count=2:  false
        */
        if (count == 1) {
            return this->square_nums.find(n) != this->square_nums.end();
        }
        for (auto &x:this->square_nums) { // 用完全平方数做检查
            if (is_divided(n - x, count - 1)) {
                return true;
            }
        }
        return false;
    }
};

class Solution2 {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) { //  遍历1到n
            int minn = INT_MAX;
            for (int j = 1; j * j <= i; j++) { // 遍历1到平方根
                minn = min(minn, dp[i - j * j]);
            }
            dp[i] = minn + 1;
        }
        return dp[n];
    }
};

int main() {
    Solution2 sol;
    cout << sol.numSquares(13) << endl;
    return 0;
}
